package com.ww.springboot.boot.algorithm.leetcode2;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2025-05-21 10:27
 */
public class B3356零数组变换2 {

    public static void main(String[] args) {
        int[] nums = {2,0,2};
        int[][] queries = {{0,2,1}, {0,2,1},{1,1,3}};

        int i = minZeroArray2(nums, queries);
        System.out.println(i);
    }

    /**
     * 顺序遍历queries 直到nums中都变成0为止
     *
     * @param nums
     * @param queries
     * @return
     */
    public static int minZeroArray(int[] nums, int[][] queries) {
        int zeroSize = 0;
        for (int num : nums) {
            if(num == 0){
                zeroSize++;
            }
        }
        if(zeroSize == nums.length){
            return 0;
        }

        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            for (int j = query[0]; j <= query[1]; j++) {
                if(nums[j] == 0){
                    continue;
                }
                int result = nums[j] - query[2];
                if(result <=0){
                    nums[j] = 0;
                    zeroSize++;
                }else {
                    nums[j] = result;
                }
            }
            if(zeroSize == nums.length){
                return i + 1;
            }
        }
        return -1;
    }

    /**
     * 将操作数累加 累加到deltaArray中
     * 可以避免每次都计算nums
     *
     * @param nums
     * @param queries
     * @return
     */
    public static int minZeroArray2(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] deltaArray = new int[n + 1];
        int operations = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            operations += deltaArray[i];
            while (k < queries.length && operations < num) {
                int left = queries[k][0];
                int right = queries[k][1];
                int value = queries[k][2];
                deltaArray[left] += value;
                deltaArray[right + 1] -= value;
                if (left <= i && i <= right) {
                    operations += value;
                }
                k++;
            }
            if (operations < num) {
                return -1;
            }
        }
        return k;
    }
}
